package algorithms.leaning.class20;

import common.util.MyUtil;

/**
 * 范围尝试模型，以什么开头或者结尾
 * 给定一个字符串str，返回这个字符串的最长回文子序列长度
 * 比如 ： str = “a12b3c43def2ghi1kpm”
 * 最长回文子序列是“1234321”或者“123c321”，返回长度7
 *
 * @author guichang
 * @date 2021/6/21
 */

@SuppressWarnings("all")
public class Code1_动态规划_最长回文子序列 {
    public static void main(String[] args) {
        String str = "a12b3444443def2ghi1kpm";
        MyUtil.print(longestPalindromeSubsequence(str));
        MyUtil.print(longestPalindromeSubsequenceDp(str));
    }

    public static int longestPalindromeSubsequence(String str) {
        if (str == null) {
            return 0;
        }
        return process(str.toCharArray(), 0, str.length() - 1);
    }

    /**
     * L~R范围内最长回文子序列长度
     */
    private static int process(char[] cs, int L, int R) {
        // 注意控制L R都不能越界
        if (R - L == 0) {
            return 1;
        }
        if (R - L == 1) {
            return cs[L] == cs[R] ? 2 : 1;
        }
        int p1 = process(cs, L + 1, R);
        int p2 = process(cs, L, R - 1);
        int p3 = cs[L] == cs[R] ? (2 + process(cs, L + 1, R - 1)) : 0;
        return Math.max(p3, Math.max(p1, p2));
    }

    public static int longestPalindromeSubsequenceDp(String str) {
        if (str == null) {
            return 0;
        }
        char[] cs = str.toCharArray();
        int N = cs.length;
        int[][] dp = new int[N][N];
        // 斜对角填好
        for (int i = 0; i < N; i++) {
            dp[i][i] = 1;
            if (i + 1 < N) {
                dp[i][i + 1] = cs[i] == cs[i + 1] ? 2 : 1;
            }
        }
        // 其他的需要斜着填
        for (int i = 2; i < N; i++) {
            int L = 0;
            int R = i;
            while (R < N) {
                int p1 = dp[L + 1][R];
                int p2 = dp[L][R - 1];
                int p3 = cs[L] == cs[R] ? (2 + dp[L + 1][R - 1]) : 0;
                dp[L][R] = Math.max(p3, Math.max(p1, p2));
                L++;
                R++;
            }
        }
        return dp[0][N - 1];
    }
}